package pro.softzhang.algo.lc900;

import pro.softzhang.algo.flag.theme.TMath;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 */
@TMath
public class LC970_PowerfulIntegers {
    public static void main(String[] args) {

    }

    @XOptimal
    static
    class Solution {
        public List<Integer> powerfulIntegers(int x, int y, int bound) {
            Set<Integer> ps = new HashSet<>();
            for(int a = 1; a < bound; a *= x) {
                for (int b = 1; a + b <= bound; b *= y) {
                    ps.add(a + b);
                    if (y == 1) break;
                }
                if (x == 1) break;
            }
            return new ArrayList<>(ps);
        }
    }
}
